package com.linyaonan.leetcode.easy._876;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Lin
 * @date: 2020/1/12
 */
public class MiddleLinkedList {
    public ListNode middleNode(ListNode head) {
        List<ListNode> save = new ArrayList<>();
        while (head != null) {
            save.add(head);
            head = head.next;
        }
        int index = save.size() / 2;
        return save.get(index);
    }

    /**
     * 使用快慢指针的思想，慢指针走一步，快指针走两步，当快指针到尾部后，慢指针指向中间节点
     * @param head
     * @return
     */
    public ListNode middleNode2(ListNode head) {
        ListNode h = head;
        ListNode l = head;

        while (h != null && h.next != null) {
            h = h.next.next;
            l = l.next;
        }

        return l;
    }
}
